A content addressable memory ("CAM") is a memory device in which data is accessed and modified based upon the content of the stored data, rather than on the location in which that data is stored. A CAM generally includes multiple data storage locations comprising multiple memory cells. Unlike random access memory ("RAM"), all data words in the storage locations of a CAM may be simultaneously compared with a search word stored in a comparand register. As each stored data word is compared with the search word, a match line for that stored data word is activated if that stored data word matches the search word.
A CAM of 2.sup.N data words has 2.sup.N match lines, one match line for each data word. Each data word and match line combination has a unique N-bit address within the CAM. For any match cycle there may be zero, one, or up to 2.sup.N match lines activated. The function of a priority encoder is to generate an output address responsive to the state of the match lines. In particular, a priority encoder generates an output address corresponding to the address of the highest priority activated match line. Typically, a simple sequential priority scheme is used, the lowest address having the highest priority and the highest address having the lowest priority. In general, priority encoders may be used in both CAM and non-CAM applications, for providing a priority-encoded address of a highest priority active request line among a plurality of request lines.
FIG. 1 shows a priority encoder 10 according to the prior art using purely combinatorial logic without feedback. Priority encoder 10 is described in U.S. Pat. No. 5,123,105, entitled "Priority Encoder for a Content Addressable Memory," the disclosure of which is hereby incorporated by reference into the present application. Priority encoder 10 uses purely combinatorial logic in that no delay elements are used. The priority encoder of FIG. 1 is without feedback in that the priority-encoded address bits A0, A1, and A2 are generated by circuits which operate independently of each other, and no feeding back of intermediate results from the computation of a first of these priority-encoded address bits is necessary in order to compute the value of a second of these priority-encoded address bits. For example, the logical value of lower order bit A0 does not depend on any results associated with the computation of higher order bits A1 or A2. Rather, lower order bit A0 is computed in parallel with higher order bits A1 and A2 as a direct boolean function of the input match lines or request lines D0-D7.
Priority encoder 10 priority-encodes eight input request lines D0-D7 into a 3-bit priority-encoded address having address bits A2, A1, and A0. To provide for expansion to a greater number of input request lines, three control signals are provided including an enable input signal EI, an enable output signal EO, and a group select signal GS. To expand the number of input lines, several of these priority encoders are daisy-chained using the EI, EO, and GS signals. For example, to accommodate 64 input lines D0-D63, eight priority encoders such as priority encoder 10 are used, a first priority encoder 10 receiving lines D0-D7, a second priority encoder 10 receiving lines D8-D15, a third priority encoder 10 receiving lines D16-D23, and so on, up to an eighth priority encoder 10 receiving lines D56-D63. In a serial fashion, the EO output of the first priority encoder 10 is connected to the EI input of the second priority encoder 10, the EO output from the second priority encoder 10 is connected to the EI input of the third priority encoder 10, and so on. The outputs A2, A1, and A0 of the eight respective priority encoders 10, which are designed to be in a high-impedance state unless enabled, are simply wired together to form an overall output A2, A1, and A0. Finally, the output GS of each of the eight priority encoders 10 is provided as a data line input into a ninth priority encoder 10, with the EO output of the eighth priority encoder 10 being connected to the EI input of the ninth priority encoder 10.
As described in U.S. Pat. No. 5,123,105, supra, the signals GS and EO are complementary. When coupled as described above, the first eight priority encoders 10 form a first portion for generating bits A2, A1, and A0 of a six-bit priority-encoded address, while the ninth priority encoder 10 forms a second portion for generating bits A5, A4, and A3 of the six-bit priority-encoded address.
The priority encoder 10, as well as the above-described daisy chaining scheme for expanding the number of request lines, has several disadvantages. First, the number of gates required is excessive, requiring large amounts of power and integrated circuit chip area. Second, as the number of input lines grows, the overall response time, i.e., the time from when the first EI signal is activated until the priority-encoded address can be read from the output lines, grows enormously because of the series propagation of enable signals through the daisy chain. For example, if the EI-to-EO propagation delay of the priority encoder 10 is a typical value of 6 ns, which corresponds to the propagation delay of two logic gates at 3 ns each, the overall response time would exceed 24 ns for a 64-line configuration, 48 ns for a 128-line configuration, and 96 ns for a 256-line configuration. However, if the number of request lines for each of the priority encoders 10 were increased to reduce this propagation delay, the overall number of gates would become extremely and unrealistically excessive.
FIG. 2 shows a priority encoder 100 according to the prior art designed to solve some of the above problems, the priority encoder 100 using delay lines and having feedback. Such a priority encoder is disclosed in U.S. Pat. No. 5,123,105, supra. The priority encoder 100 of FIG. 2 is a 16-line priority encoder having 16 input lines D0-D15, a node EN for receiving an enable signal, and four output lines A3-A0 for providing a priority-encoded output address.
Starting with the highest order priority-encoded address bit A3, the priority encoder 100 sequentially generates each priority-encoded address bit based on (a) the state of the input request lines D0-D15, and (b) results from previously generated output bits. When the signal EN is activated, the value of the most significant address bit A3 is computed by a first address bit generation circuit 150, and the remainder of the priority encoder circuit 100 remains disabled. Once A3 is determined, its value is provided at a node 242 for driving the gates of transistors 278-292. Intermediate signals at nodes 178-192 are thereby determined, these signals being provided to the remainder of the priority encoder 100. After a predetermined time, as dictated by the time constant of a delay element 300, a second address bit generation circuit 152 is activated for determining the value of the second-highest order bit A2. After a second predetermined time, as dictated by the time constant of a delay element 366, a third address bit generation circuit 154 is activated, and so on.
Unlike the priority encoder of FIG. 1, the priority encoder of FIG. 2 has feedback in that results from the determination of a higher order address bit is used in the determination of a lower order address bit. By using feedback, the priority encoder 100 of FIG. 2 is capable of generating a priority-encoded address using fewer elements and less integrated circuit chip area than the priority encoder of FIG. 1, especially as the number of address bits N and request lines 2.sup.N grows large.
The priority encoder of FIG. 2, however, contains several disadvantages. One disadvantage is the large amount of capacitance at major switching nodes such as nodes 246, 248, 328, and 344. This causes excessive propagation delays between successive computations of the priority-encoded address bits A-A0. For example, if all inputs D0-D15 are low and then input D3 rises, it may take in excess of 20 ns for node A3 to go from low to high. For proper functioning, the delay time assigned to each of the delay elements, such as element 300, must be greater than the slowest rise time of its associated priority-encoded address bit, such as bit A3. Because each delay element must have an exemplary delay of, for example, 25 ns, the overall response time of the priority encoder 100 may exceed 100 ns.
A second disadvantage of the priority encoder 100 is that it uses delay elements, which is a generally undesirable practice in integrated circuit design. This problem may be avoided by synchronizing the successive activation of circuit portions 150-156 by using clock signals. However, the synchronization of the circuit 100 adds its own complexities, and does not reduce the capacitance, the required computation time, and the serial triggering requirements of circuit portions 150-156, and thus does not appreciably reduce the overall response time of the priority encoder 100.
For the priority encoder 100 of FIG. 2, the above capacitance and propagation delay problems worsen as the number of request lines increases. In particular, as the number of input lines is increased, the number of NMOS gates at nodes 268, 344, etc., must increase approximately linearly with the number of request lines. The capacitance and propagation delay at each stage of the priority encoder 100 grows accordingly. As a result, an exemplary priority encoder designed in accordance with FIG. 2 and having 128 lines may have an overall response time in excess of 500 ns. Such response times become even more intolerable for larger priority encoders. Additionally, the larger capacitances also necessitate larger driving currents and greater power consumption.
It is therefore desirable to provide a priority encoder for reliably generating priority-encoded addresses for large CAM arrays.
It is also desirable to provide a priority encoder which has faster response times in the generation of priority-encoded addresses even for large CAM arrays.
It is also desirable to provide a priority encoder which uses acceptable amounts of integrated circuit chip space and power.
It is also desirable to provide a priority encoder which is reliable and stable and does not necessitate the use of clocks or delay elements.